<!DOCTYPE html>
<html>

<head>
    <meta charset='utf-8'>
    <meta http-equiv='X-UA-Compatible' content='IE=edge'>
    <title>007-单词拆分</title>
    <meta name='viewport' content='width=device-width, initial-scale=1'>

</head>

<body>
    <div class="box">
        <div class="left-wrap">

        </div>
    </div>
</body>
<script>
    /*
   给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

    说明：

    拆分时可以重复使用字典中的单词。
    你可以假设字典中没有重复的单词。
    示例 1：

    输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
    示例 2：

    输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
        注意你可以重复使用字典中的单词。
    示例 3：

    输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false
    */
    /**
    * @param {string} s
    * @param {string[]} wordDict
    * @return {boolean}
    */
    var wordBreak = function (s, wordDict) {
        // dp[i]表示0-i之间的字符串是否可以被拆分并满足题设条件存在于wordDict中
        let dp = new Array(s.length).fill(false);
        let set = new Set(wordDict);
        for (let i = 0; i < s.length; i++) {
            // 检查0-i之间的字符串是否直接存在于wordDict中
            if (set.has(s.substring(0, i + 1))) {
                dp[i] = true;
                continue;
            }
            // 这一步是为了检查。假如s.substring(0,i)不直接存在于wordDict中
            // 那么判断拆分之后是否存在于wordDict中
            for (let j = 0; j < i; j++) {
                if (dp[j] && set.has(s.substring(j + 1, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        console.log(dp)
        debugger
        return dp[s.length - 1]
    };
    var wordBreak2 = function (s, wordDict) {
        // 与方法一类似，但是此处dp[i]表示从下标0开始长度为i的的字符串是否满足题意要求，可以被拆分并存在与wordDict中
        let dp = new Array(s.length + 1).fill(false);
        let set = new Set(wordDict);

        // 因为dp[i]的i表示长度，因此dp[0]=true
        dp[0] = true;
        // for中的i表示从下标0开始字符串的长度，因此从1开始
        for (let i = 1; i < s.length + 1; i++) {
            // 判断s[j-i]是否满足题目要求
            // 注意此处是j<i不是j<=i
            for (let j = 0; j < i; j++) {
                if (dp[j] && set.has(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length];
    };
    const s = "leetcode", wordDict = ["leet", "code"]
    console.log(wordBreak(s, wordDict))
</script>

</html>